{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Permutation in String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #two-pointers #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #双指针 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkInclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串的排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>s1</code>&nbsp;和&nbsp;<code>s2</code> ，写一个函数来判断 <code>s2</code> 是否包含 <code>s1</code><strong>&nbsp;</strong>的排列。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>换句话说，<code>s1</code> 的排列之一是 <code>s2</code> 的 <strong>子串</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"ab\" s2 = \"eidbaooo\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>s2 包含 s1 的排列之一 (\"ba\").\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1= \"ab\" s2 = \"eidboaoo\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s1.length, s2.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s1</code> 和 <code>s2</code> 仅包含小写字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [permutation-in-string](https://leetcode.cn/problems/permutation-in-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [permutation-in-string](https://leetcode.cn/problems/permutation-in-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ab\"\\n\"eidbaooo\"', '\"ab\"\\n\"eidboaoo\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        if len(s2) < len(s1):\n",
    "            return False\n",
    "        d2, d1 = dict(), dict()\n",
    "        for i in range(len(s1)):\n",
    "            d1[s1[i]] = d1.get(s1[i],0)+1\n",
    "            d2[s2[i]] = d2.get(s2[i],0)+1\n",
    "        \n",
    "        if d1 == d2:\n",
    "            return True\n",
    "        \n",
    "        for i in range(len(s1), len(s2)):\n",
    "            d2[s2[i]] = d2.get(s2[i],0)+1\n",
    "            d2[s2[i - len(s1)]] -= 1\n",
    "            if d2[s2[i - len(s1)]] == 0:  # remove empty keys, otherwise compare will fail\n",
    "                d2.pop(s2[i - len(s1)])\n",
    "            \n",
    "            if d1 == d2:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(s2) < len(s1) or len(s2) == 0:\n",
    "            return False\n",
    "        \n",
    "        d_s1 = [0] * 128\n",
    "        d_s2 = [0] * 128\n",
    "        for i in range(len(s1)):\n",
    "            d_s1[ord(s1[i])] += 1\n",
    "            d_s2[ord(s2[i])] += 1\n",
    "        \n",
    "        if d_s1 == d_s2:\n",
    "            return True\n",
    "        \n",
    "        for j in range(len(s1), len(s2)):\n",
    "            d_s2[ord(s2[j])] += 1\n",
    "            d_s2[ord(s2[j-len(s1)])] -= 1\n",
    "            if d_s1 == d_s2 :\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # s1c = collections.Counter(s1)\n",
    "        # tmpcol = collections.Counter(s2[:len(s1)])\n",
    "        # i,j = 0,len(s1)\n",
    "        # while j<len(s2):\n",
    "        #     acc = 1\n",
    "        #     for k in s1c.keys():\n",
    "        #         if s1c[k]==tmpcol[k]:\n",
    "        #             continue\n",
    "        #         else:\n",
    "        #             acc = 0\n",
    "        #             break\n",
    "        #     if acc:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         if s2[j] in tmpcol:\n",
    "        #             tmpcol[s2[j]]+=1\n",
    "        #         else:\n",
    "        #             tmpcol[s2[j]]=1\n",
    "        #         tmpcol[s2[i]]-=1\n",
    "        #         i+=1\n",
    "        #         j+=1\n",
    "        # return False\n",
    "        if len(s1)>len(s2):\n",
    "            return False\n",
    "        alph = list(range(ord(\"a\"),ord(\"z\")+1))\n",
    "        s1c = {chr(i):0 for i in alph}\n",
    "        tmpcol = {chr(i):0 for i in alph}\n",
    "        i = 0\n",
    "        dis = len(s1)\n",
    "        while i<len(s1)-1:\n",
    "            s1c[s1[i]]+=1\n",
    "            tmpcol[s2[i]]+=1\n",
    "            i+=1\n",
    "        s1c[s1[i]]+=1\n",
    "        while i<len(s2):\n",
    "            tmpcol[s2[i]]+=1\n",
    "            if s1c==tmpcol:\n",
    "                # print(i,tmpcol)\n",
    "                return True\n",
    "            else: \n",
    "                i+=1\n",
    "                tmpcol[s2[i-dis]]-=1\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: 'str', s2: 'str') -> 'bool':\n",
    "        A = [ord(x) - ord('a') for x in s1]\n",
    "        B = [ord(x) - ord('a') for x in s2]\n",
    "\n",
    "        target = [0] * 26\n",
    "        for x in A:\n",
    "            target[x] += 1\n",
    "\n",
    "        window = [0] * 26\n",
    "        for i, x in enumerate(B):\n",
    "            window[x] += 1\n",
    "            if i >= len(A):\n",
    "                window[B[i - len(A)]] -= 1\n",
    "            if window == target:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n1,n2=len(s1),len(s2)\n",
    "        coco=Counter(s1)\n",
    "        cx=Counter()\n",
    "        i,j=0,0\n",
    "        while i<n2:\n",
    "            if s2[i] not in coco:\n",
    "                i+=1\n",
    "                j=i\n",
    "                cx=Counter()\n",
    "            else:\n",
    "                cx[s2[i]]+=1\n",
    "                if i-j==n1-1:\n",
    "                    if cx==coco:return True\n",
    "                    i+=1\n",
    "                    cx[s2[j]]-=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def match(s1_,s2_):\n",
    "            for i in range(26):\n",
    "                if s1_[i] != s2_[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        s1_len = len(s1)\n",
    "        s2_len = len(s2)\n",
    "        \n",
    "        if s1_len > s2_len:\n",
    "            return False\n",
    "        s1_chars = list(s1)\n",
    "        s2_chars = list(s2)\n",
    "        s1_list = [0] * 26\n",
    "        s2_list = [0] * 26\n",
    "        for i in range(s1_len):\n",
    "            s1_list[ord(s1_chars[i]) - ord('a')] += 1\n",
    "            s2_list[ord(s2_chars[i]) - ord('a')] += 1\n",
    "        print(s1_list)   \n",
    "        print(s2_list)\n",
    "        for i in range(s2_len - s1_len):\n",
    "            if match(s1_list,s2_list):\n",
    "                return True\n",
    "            s2_list[ord(s2_chars[i + s1_len]) - ord('a')] += 1\n",
    "            s2_list[ord(s2_chars[i]) - ord('a')] -= 1\n",
    "        return  match(s1_list,s2_list)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        azs1 = collections.defaultdict(int)\n",
    "        for char in s1:\n",
    "            azs1[char] += 1\n",
    "\n",
    "        azs2 = collections.defaultdict(int)\n",
    "        azrecode = collections.defaultdict(list)\n",
    "        index = 0\n",
    "        i = 0\n",
    "        while i < len(s2):\n",
    "            char = s2[i]\n",
    "            if char not in azs1.keys():\n",
    "                index = i + 1\n",
    "                i = index\n",
    "                azs2 = collections.defaultdict(int)\n",
    "                azrecode = collections.defaultdict(list)\n",
    "                continue\n",
    "            azrecode[char].append(i)\n",
    "            azs2[char] += 1\n",
    "            if azs2[char] == azs1[char]:\n",
    "                if azs2==azs1:\n",
    "                    return True\n",
    "                i += 1\n",
    "            elif azs2[char] < azs1[char]:\n",
    "                i += 1\n",
    "            else:\n",
    "                left = azrecode[char].pop(0)\n",
    "                azs2[char]-=1\n",
    "                for j in range(index, left):\n",
    "                    if s2[j] in azs1.keys():\n",
    "                        azs2[s2[j]] -= 1\n",
    "                        azrecode[s2[j]].pop(0)\n",
    "                index = left + 1\n",
    "                i += 1\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        azs1={}\n",
    "        for char in s1:\n",
    "            if char not in azs1:\n",
    "                azs1[char]=1\n",
    "            else:\n",
    "                azs1[char]+=1\n",
    "                \n",
    "        azs2={}\n",
    "        for key in azs1.keys():\n",
    "            azs2[key]=0\n",
    "        \n",
    "        init_azs2=azs2.copy()\n",
    "        \n",
    "        azrecode={}\n",
    "        for key in azs1.keys():\n",
    "            azrecode[key]=[]\n",
    "        \n",
    "        init_azrecode=azrecode.copy()\n",
    "        \n",
    "        index=0\n",
    "        i=0\n",
    "        while i<len(s2):\n",
    "            char=s2[i]\n",
    "            if char not in azs1.keys():\n",
    "                index=i+1\n",
    "                i=index\n",
    "                azs2=init_azs2.copy()\n",
    "                for key in azs1.keys():\n",
    "                    azrecode[key]=[]\n",
    "                continue\n",
    "            azrecode[char].append(i)\n",
    "            azs2[char]+=1\n",
    "            if azs2[char]==azs1[char]:\n",
    "                ok=True\n",
    "                for key in azs1.keys():\n",
    "                    if azs1[key]!=azs2[key]:\n",
    "                        ok=False\n",
    "                        break\n",
    "                if ok:\n",
    "                    return True\n",
    "                i+=1\n",
    "            elif azs2[char]<azs1[char]:\n",
    "                i+=1\n",
    "            else:\n",
    "                left=azrecode[char].pop(0)\n",
    "                azs2[char]-=1\n",
    "                for j in range(index,left):\n",
    "                    if s2[j] in azs1.keys():\n",
    "                        azs2[s2[j]]-=1\n",
    "                        azrecode[s2[j]].pop(0)\n",
    "                index=left+1\n",
    "                i+=1\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        if l2 < l1:\n",
    "            return False\n",
    "        \n",
    "        dic1, dic2 = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        for ch in s1:\n",
    "            dic1[ch] += 1 \n",
    "        for i in range(l1):\n",
    "            dic2[s2[i]] += 1\n",
    "        if dic1 == dic2:\n",
    "            return True\n",
    "        for i in range(l1,l2):\n",
    "            dic2[s2[i]] += 1\n",
    "            dch = s2[i-l1]\n",
    "            dic2[dch] -= 1\n",
    "            if not dic2[dch]:\n",
    "                dic2.pop(dch)\n",
    "            if dic1 == dic2:\n",
    "                return True\n",
    "        return False\n",
    "                    \n",
    "                    \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        if l2 < l1:\n",
    "            return False\n",
    "        \n",
    "        dic1, dic2 = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        for ch in s1:\n",
    "            dic1[ch] += 1 \n",
    "        for i in range(l1):\n",
    "            dic2[s2[i]] += 1\n",
    "        if dic1 == dic2:\n",
    "            return True\n",
    "        for i in range(l1,l2):\n",
    "            dic2[s2[i]] += 1\n",
    "            dch = s2[i-l1]\n",
    "            dic2[dch] -= 1\n",
    "            if not dic2[dch]:\n",
    "                dic2.pop(dch)\n",
    "            if dic1 == dic2:\n",
    "                return True\n",
    "        return False\n",
    "                    \n",
    "                    \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
    "        for i in s1:\n",
    "            a[ord(i) - ord('a')] += 1\n",
    "        d = copy.deepcopy(a)\n",
    "\n",
    "        i = begin = count = 0\n",
    "        lens2 = len(s2)\n",
    "        lens1 = len(s1)\n",
    "        pos = ord('a')\n",
    "        while i < lens2:\n",
    "            key = ord(s2[i]) - pos\n",
    "            if a[key] == 0:\n",
    "                if d[key] == 0:\n",
    "                    begin = i + 1\n",
    "                    if count != 0:\n",
    "                        count = 0\n",
    "                        a = copy.deepcopy(d)\n",
    "                else:\n",
    "                    while begin <= i:\n",
    "                        l = (ord(s2[begin]) - pos)\n",
    "                        begin += 1\n",
    "                        if l != key:\n",
    "                            count -= 1\n",
    "                            a[l] += 1\n",
    "                        else:\n",
    "                            break\n",
    "            else:\n",
    "                a[key] -= 1\n",
    "                count += 1\n",
    "                if count == lens1:\n",
    "                    return True\n",
    "\n",
    "            i += 1\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMatch(self,str1,s2):\n",
    "        s1=str1\n",
    "        n = len(s2)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            index = s1.find(s2[i])\n",
    "            if index == -1:\n",
    "                return i\n",
    "            else:\n",
    "                s1 = s1[:index]+s1[index+1:]\n",
    "        return -1\n",
    "    \n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if s1==\"\":\n",
    "            return True\n",
    "        if s2==\"\":\n",
    "            return False\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "        i = 0\n",
    "        while i<n:\n",
    "            if i+m>n:\n",
    "                return False\n",
    "            index = self.isMatch(s1,s2[i:i+m])\n",
    "            if index== -1:\n",
    "                return True\n",
    "            i = i + index + 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def h(self, s):\n",
    "        v = 0\n",
    "        for i in s:\n",
    "            v += hash(i)\n",
    "        return v\n",
    "\n",
    "    def h2(self, s, width):\n",
    "        v = self.h(s[: width])\n",
    "        yield v\n",
    "        for i in range(len(s) - width):\n",
    "            v = v - hash(s[i]) + hash(s[i + width])\n",
    "            yield v\n",
    "\n",
    "    def checkInclusion(self, s1, s2):\n",
    "        \"\"\"\n",
    "        :type s1: str\n",
    "        :type s2: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(s2) < len(s1):\n",
    "            return False\n",
    "        hash_code = self.h(s1)\n",
    "        for i in self.h2(s2, len(s1)):\n",
    "            if hash_code == i:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import Counter\n",
    "        counter1 = Counter(list(s1))\n",
    "        counter2 = Counter(list(s2[:len(s1)]))\n",
    "        print(counter1, counter2)\n",
    "        if counter1 == counter2:\n",
    "            return True\n",
    "        for i in range(len(s2)-len(s1)):\n",
    "            counter2[s2[i]] -= 1\n",
    "            if counter2[s2[i]] == 0:\n",
    "                counter2.pop(s2[i])\n",
    "            counter2[s2[i + len(s1)]] += 1\n",
    "            if counter1 == counter2:\n",
    "                return True\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        c1 = collections.Counter(s1)\n",
    "        c2 = collections.Counter()\n",
    "        cnt = 0 #统计变量，全部26个字符，频率相同的个数，当cnt==s1字母的个数的时候，就是全部符合题意，返回真\n",
    "        p = q = 0 #滑动窗口[p,q]\n",
    "        while q < l2:\n",
    "            c2[s2[q]] += 1\n",
    "            if c1[s2[q]] == c2[s2[q]]: #对于遍历到的字母，如果出现次数相同\n",
    "                cnt += 1               #统计变量+1\n",
    "            if cnt == len(c1):         #判断结果写在前面，此时证明s2滑动窗口和s1全部字符相同，返回真\n",
    "                return True\n",
    "            q += 1                     #滑动窗口右移\n",
    "            if q - p + 1 > l1:         #这是构造第一个滑动窗口的特殊判断，里面内容是维护边界滑动窗口\n",
    "                if c1[s2[p]] == c2[s2[p]]:    #判断性的if写在前面，因为一旦频率变化，这个统计变量就减1\n",
    "                    cnt -= 1\n",
    "                c2[s2[p]] -= 1                #字典哈希表移除最前面的字符\n",
    "                if c2[s2[p]] == 0:            #由于counter特性，如果value为0，必须删除它\n",
    "                    del c2[s2[p]]\n",
    "                p += 1                        #最前面的下标右移动\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        if n1 > n2:\n",
    "            return False\n",
    "        print([n1,n2])\n",
    "        counter_ori = {}\n",
    "        counter_cur = {}\n",
    "        n = 0\n",
    "        for i in s1:\n",
    "            counter_ori[i] = counter_ori.get(i, 0)+1\n",
    "        for end in range(n2): # 移动end指针\n",
    "            # end指针移动更新计数信息\n",
    "            if s2[end] in counter_ori:\n",
    "                counter_cur[s2[end]] = counter_cur.get(s2[end], 0)+1\n",
    "            n += 1\n",
    "            #print(s2[end-n+1:end+1])\n",
    "            #print(counter_cur)\n",
    "            # 固定长度滑动窗，left直接通过推算得到\n",
    "            if n == n1 and counter_cur==counter_ori: \n",
    "                return True\n",
    "            # left指针移动，更新计数板信息\n",
    "            if n==n1:\n",
    "                n-=1\n",
    "                if s2[end-n1+1] in counter_cur:\n",
    "                    counter_cur[s2[end-n1+1]] -= 1\n",
    "        return False\n",
    "            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        if s1 == '':\n",
    "            return True\n",
    "        else:\n",
    "            if s2 == '':\n",
    "                return False\n",
    "            # 划窗\n",
    "            else:\n",
    "                for i in range(0, len(s2)-len(s1)+1):\n",
    "                    if self.AperB(s1, s2[i:i+len(s1)]):\n",
    "                        return True\n",
    "                return False\n",
    "    \n",
    "    def AperB(self, str1, str2):\n",
    "        # 判断A和B是不是互为排列\n",
    "        dictA = {}; dictB = {}\n",
    "        for c1 in str1:\n",
    "            if c1 not in dictA:\n",
    "                dictA[c1] = 0\n",
    "            else:\n",
    "                dictA[c1] += 1\n",
    "        for c2 in str2:\n",
    "            if c2 not in dictB:\n",
    "                dictB[c2] = 0\n",
    "            else:\n",
    "                dictB[c2] += 1\n",
    "        return dictA == dictB\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        s1_dict = defaultdict(int)\n",
    "        for s in s1:\n",
    "            s1_dict[s] += 1\n",
    "        s1_dict2 = defaultdict(int)\n",
    "        i = 0\n",
    "        while i + len(s1) <= len(s2):\n",
    "            flag = 1\n",
    "            if s1_dict[s2[i]] > 0:\n",
    "                for j in range(0,len(s1)):\n",
    "                    s1_dict2[s2[i+j]] += 1\n",
    "                    if s1_dict2[s2[i+j]] <= s1_dict[s2[i+j]]:\n",
    "                        flag = 0\n",
    "                    else:\n",
    "                        flag = 1\n",
    "                        s1_dict2 = defaultdict(int)                        \n",
    "                        break\n",
    "            i += 1\n",
    "            if flag == 0:return True             \n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import Counter\n",
    "\n",
    "        cnt1 = Counter(s1)\n",
    "        # cnt2 = Counter(s2)\n",
    "\n",
    "        for i in range(len(s2)-len(s1)+1):\n",
    "            if Counter(s2[i:i+len(s1)]) == cnt1:\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        def slidingWindows(s,t): # source, target\n",
    "            need = collections.Counter(t) # 需要出现的次数\n",
    "            windows = dict.fromkeys(need.keys(),0) # 窗口中出现的次数\n",
    "            left = right = 0 # 左右指针表示窗口[left,right)\n",
    "            valid = 0 # 表示窗口中满足need条件的字符个数\n",
    "            while right < len(s):\n",
    "                c = s[right] # 移入窗口的字符\n",
    "                right += 1\n",
    "                # 窗口内数据的更新\n",
    "                if c in need:\n",
    "                    windows[c] += 1\n",
    "                    if windows[c] == need[c]:\n",
    "                        valid += 1\n",
    "                while right - left > len(t): # 左窗口需要收缩\n",
    "                    d = s[left] # 移出窗口的字符\n",
    "                    left += 1\n",
    "                    # 窗口内数据的更新\n",
    "                    if d in need:\n",
    "                        if windows[d] == need[d]:\n",
    "                            valid -= 1\n",
    "                        windows[d]-= 1\n",
    "                if valid == len(need):\n",
    "                    return True\n",
    "            return False\n",
    "        return slidingWindows(s2,s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        if len(s1) > len(s2):\n",
    "            return False\n",
    "        cl = {k:0 for k in string.ascii_lowercase}\n",
    "        cur = {k:0 for k in string.ascii_lowercase}\n",
    "        for a in s1: cl[a] += 1\n",
    "        for i in range(len(s2)):\n",
    "            cur[s2[i]] += 1\n",
    "            if i >= len(s1):\n",
    "                cur[s2[i - len(s1)]] -= 1\n",
    "            if cl == cur: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        if len(s1) > len(s2):\n",
    "            return False\n",
    "        s1 = sorted(s1)\n",
    "        for i in range(len(s2)-len(s1)+1):\n",
    "            if sorted(s2[i:i+len(s1)]) == s1:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def checkInclusion(self, s1: str, s2: str):\r\n",
    "\r\n",
    "        # 思路：滑动窗口 双指针\r\n",
    "        # 不需要在意target str的位置排序，只要其为与window中即可\r\n",
    "        # 1、确定目标\r\n",
    "        # 2、扩展right直至包含目标\r\n",
    "        # 3、收缩left，若window大小等于len(s2)则return true\r\n",
    "\r\n",
    "        need = Counter(s1)\r\n",
    "        window = dict()\r\n",
    "        filter_s = []\r\n",
    "        for i, c in enumerate(s2):\r\n",
    "            if c in need:\r\n",
    "                filter_s.append((i, c))\r\n",
    "        \r\n",
    "        left, right = 0, 0\r\n",
    "\r\n",
    "        valid = 0\r\n",
    "\r\n",
    "        while right < len(filter_s):\r\n",
    "            r_c = filter_s[right][1]\r\n",
    "            window[r_c] = window.get(r_c, 0) + 1\r\n",
    "            if window[r_c] == need[r_c]:\r\n",
    "                valid += 1\r\n",
    "            while valid >= len(need):\r\n",
    "                temp_len = filter_s[right][0] - filter_s[left][0] + 1\r\n",
    "                if temp_len == len(s1):\r\n",
    "                    return True\r\n",
    "\r\n",
    "                l_c = filter_s[left][1]\r\n",
    "                if window[l_c] == need[l_c]:\r\n",
    "                    valid -= 1\r\n",
    "                window[l_c] -= 1\r\n",
    "                         \r\n",
    "                left += 1\r\n",
    "\r\n",
    "            right += 1\r\n",
    "\r\n",
    "        return False\r\n",
    "\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        l, r = 0, len(s1) - 1\n",
    "        while r < len(s2):\n",
    "            if self.havePermutation(s1, s2, l, r):\n",
    "                return True\n",
    "            l += 1\n",
    "            r += 1\n",
    "        return False\n",
    "\n",
    "    def havePermutation(self, s1, s2, l, r):\n",
    "        cdict = {}\n",
    "        for c in s1:\n",
    "            if c not in cdict:\n",
    "                cdict[c] = 0\n",
    "            cdict[c] += 1\n",
    "        for c in s2[l:r + 1]:\n",
    "            if c not in cdict:\n",
    "                return False\n",
    "            cdict[c] -= 1\n",
    "        for c in cdict:\n",
    "            if cdict[c] != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        counter1 = collections.Counter(s1)\n",
    "        N = len(s2)\n",
    "        # 定义滑动窗口的范围是 [left, right]，闭区间，长度与s1相等\n",
    "        left = 0\n",
    "\n",
    "        # 统计窗口s2[left, right - 1]内的元素出现的次数\n",
    "\n",
    "        while left < N - len(s1) + 1:\n",
    "            right = len(s1) + left\n",
    "            counter2 = collections.Counter(s2[left:right])\n",
    "            if counter1 == counter2:\n",
    "                return True\n",
    "            left += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "#         if len(s1) > len(s2): return False\n",
    "#         s1_count={}\n",
    "#         for char in s1:\n",
    "#             s1_count[char] = s1_count.get(char,0)+1\n",
    "# # dict.get(key, default=None)返回指定键的值，如果键不在字典中返回 default 设置的默认值\n",
    "        \n",
    "#         # 第一个窗口\n",
    "#         left,right=0,len(s1)-1\n",
    "#         window_counts={}       \n",
    "#         for i in range (left,right+1):\n",
    "#             if s2[i] in s1:\n",
    "#                 window_counts[s2[i]] = window_counts.get(s2[i],0)+1       \n",
    "        \n",
    "#         if sorted(s1_count.items()) == sorted(window_counts.items()): return True      \n",
    "#         else:  \n",
    "#             while right <len(s2)-1:\n",
    "#                 right+=1\n",
    "#                 left+=1\n",
    "#                 if s2[right] in s1:\n",
    "#                     window_counts[s2[right]] = window_counts.get(s2[right],0)+1\n",
    "#                 if s2[left] in s1:\n",
    "#                     window_counts[s2[left]] -=1\n",
    "                \n",
    "#                 if sorted(s1_count.items()) == sorted(window_counts.items()): \n",
    "#                     return True \n",
    "#                     break\n",
    "                \n",
    "#         return False\n",
    "\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        if len(s1) > len(s2): return False\n",
    "        s1_count = Counter(s1)\n",
    "\n",
    "        # 第一个窗口\n",
    "        left,right = 0,len(s1)-1\n",
    "        window_counts = Counter(s2[left:right+1])\n",
    "\n",
    "        if s1_count == window_counts: return True      \n",
    "        else:  \n",
    "            while right < len(s2)-1:\n",
    "                right += 1\n",
    "                left += 1\n",
    "                window_counts[s2[right]] += 1\n",
    "                window_counts[s2[left-1]] -= 1\n",
    "\n",
    "                if s1_count == window_counts: \n",
    "                    return True \n",
    "                    break\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        windows, need = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        for c in s1:\n",
    "            need[c] += 1\n",
    "        left, right = 0, 0 \n",
    "        valid = 0\n",
    "        while right < len(s2):\n",
    "            c = s2[right]\n",
    "            right += 1\n",
    "            if c in need:\n",
    "                windows[c] += 1\n",
    "                if windows[c] == need[c]:\n",
    "                    valid += 1\n",
    "            while right - left >= len(s1):\n",
    "                if valid == len(need):\n",
    "                    return True\n",
    "                d = s2[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if windows[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    windows[d] -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        need, window = defaultdict(int), defaultdict(int)\n",
    "\n",
    "        for i in s1:\n",
    "            need[i] += 1\n",
    "        \n",
    "        left, right, valid = 0, 0, 0\n",
    "        while right < len(s2):\n",
    "            r = s2[right]\n",
    "            right += 1\n",
    "            if r in need:\n",
    "                window[r] += 1\n",
    "                if window[r] == need[r]:\n",
    "                    valid += 1\n",
    "            \n",
    "            while left < right and valid == len(need):\n",
    "                if right - left  == len(s1):\n",
    "                    return True\n",
    "\n",
    "                l = s2[left]\n",
    "                left += 1\n",
    "                if l in need:\n",
    "                    if window[l] == need[l]:\n",
    "                        valid -= 1\n",
    "                    window[l] -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        hashs1={}\n",
    "        hashs2={}\n",
    "        start=0\n",
    "        for i in range(len(s1)):\n",
    "            hashs1[s1[i]]=hashs1.get(s1[i],0)+1\n",
    "        for end in range(len(s2)):\n",
    "            hashs2[s2[end]]=hashs2.get(s2[end],0)+1\n",
    "            print(hashs2)\n",
    "           # if end-start+1 ==len(s1):\n",
    "            if hashs1==hashs2:\n",
    "                return True\n",
    "                \n",
    "                    \n",
    "\n",
    "            if end -start+1>= len(s1):\n",
    "                hashs2[s2[start]]=hashs2[s2[start]]-1\n",
    "                if hashs2[s2[start]]==0:\n",
    "                    del hashs2[s2[start]]\n",
    "\n",
    "                \n",
    "                start+=1\n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        if n1 > n2:\n",
    "            return False\n",
    "\n",
    "        # compare the ASCII sum and character set of n1-length substring of s2 with s1\n",
    "        s1_sum = sum(ord(c1) for c1 in s1)\n",
    "        s2_sum = [sum(ord(c2) for c2 in s2[:n1])] + [0]*(n2-n1)\n",
    "        s1 = set(s1)\n",
    "        if s2_sum[0] == s1_sum and set(s2[:n1]) == s1:\n",
    "            return True\n",
    "\n",
    "        for i in range(1, n2-n1+1):\n",
    "            s2_sum[i] = s2_sum[i-1] + ord(s2[i+n1-1]) - ord(s2[i-1])\n",
    "            if s2_sum[i] == s1_sum and set(s2[i:i+n1]) == s1:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        if n1 > n2:\n",
    "            return False\n",
    "        table1, table2 = [0] * 26, [0] * 26\n",
    "        for i in range(n1):\n",
    "            table1[ord(s1[i]) - ord('a')] += 1\n",
    "            table2[ord(s2[i]) - ord('a')] += 1\n",
    "        if table1 == table2:\n",
    "            return True\n",
    "        for i in range(n1, n2):\n",
    "            table2[ord(s2[i]) - ord('a')] += 1\n",
    "            table2[ord(s2[i-n1]) - ord('a')] -= 1\n",
    "            if table1 == table2:\n",
    "                return True\n",
    "        return False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--f7a92/\n",
    "# 考察滑窗\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    # 判断 s 中是否存在 t 的排列\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        windows = defaultdict(int)\n",
    "        left, right = 0, 0\n",
    "\n",
    "        need = defaultdict(int)\n",
    "        valid = 0\n",
    "        for i in s1:\n",
    "            need[i] += 1\n",
    "\n",
    "        while right < len(s2):\n",
    "            c = s2[right]\n",
    "            right += 1\n",
    "\n",
    "            if c in need:\n",
    "                windows[c] += 1\n",
    "                if windows[c] == need[c]:\n",
    "                    valid += 1\n",
    "           \n",
    "            while right - left == len(s1):\n",
    "                if valid == len(need):\n",
    "                    return True\n",
    "\n",
    "                d = s2[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if windows[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    windows[d] -= 1\n",
    "        return False\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        if len(s1) > len(s2):\n",
    "            return False\n",
    "        from collections import Counter\n",
    "        c = Counter(s1)\n",
    "        total = len(s1)\n",
    "\n",
    "    \n",
    "        l, r = 0, len(s1) - 1\n",
    "\n",
    "        for i in range(l, r+1):\n",
    "            if s2[i] in c:\n",
    "                c[s2[i]] -= 1\n",
    "                if c[s2[i]] >= 0:\n",
    "                    total -= 1\n",
    "        if total == 0:\n",
    "            return True\n",
    "        while r < len(s2) - 1:\n",
    "            if s2[l] in c:\n",
    "                c[s2[l]] += 1\n",
    "                if c[s2[l]] > 0:\n",
    "                    total += 1\n",
    "            l += 1\n",
    "            r += 1\n",
    "            if s2[r] in c:\n",
    "                c[s2[r]] -= 1\n",
    "                if c[s2[r]] >= 0:\n",
    "                    total -= 1\n",
    "            if total == 0:\n",
    "                return True\n",
    "        return False\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
